public class Sort {
    public void directInsertSort(int[] arr) {
        /**
         * 直接插入排序：
         *  时间复杂度：O(n*log n)
         *  不稳定
         *  排序思想：
         *    假设第一个元素有序，从第二个元素开始向前比较，若是前面比当前大，则交换位置
         *    直到下标走到-1或者前面的元素不比它大为止
         * */
        // 1 预处理
        int n = arr.length;

        // 2 开始排序（从1开始，假设第一个元素有序）
        for(int i = 1; i < n; i++) {
            // -保存当前元素（因为后续会被覆盖）
            int temp = arr[i];
            // -往前找适合temp的位置（就是找到第一个小于等于temp的位置，在步进的过程中已经将元素往后挪了，所以找到直接插入）
            int j = i-1;
            while(j != -1 && arr[j] > temp) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp;
        }
    }

    public void shellSort(int[] arr) {
        /**
         * 希尔排序
         *  思想：先逐步缩小增量分组预排序，再统一当成一组进行排序
         *  其中每组之间的排序都是采用直接插入排序，而分组参数gap一般采用n/2*/

        // 1 预处理
        int n = arr.length;

        // 2 排序（gap一般设定为n/2，每次折半递减）
        int g = n/2;
        while(g >= 1) {
            // --内部每组间使用直接插入排序--
            for(int i = g; i < n; i++) {
                // -保存当前比较值
                int temp = arr[i];
                // -以g为步进
                int j = i - g;
                while(j >= 0 && arr[j] > temp) {
                    arr[j+g] = arr[j];
                    j -= g;
                }
                arr[j+g] = temp;
            }
            // -更新gap值
            g /= 2;
        }
    }

    public void directSelectSort(int[] arr) {
        /**
         * 直接选择排序
         *  遍历i，j=i+1，让j遍历后续元素，找到后续中最小的元素进行与i位置元素进行交换
         *  时间复杂度O(n*n)
         *  不稳定
         *  */
        // 1 预处理
        int n = arr.length;

        // 2 直接插入排序
        for(int i = 0; i < n; i++) {
            // -先价值i位置为最小值
            int minIndex = i;
            for(int j = i+1; j < n; j++) {
                // -找到最小值，记录其下标
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 3 找到待排序区间最小值，与当前位置元素进行交换（即当前位置有序）
            swap(arr, i, minIndex);
        }
    }

    public void doubleDirectionSelectSort(int[] arr) {
        /**
         * 双向选择排序
         *  同时找到有效区间中的最大值和最小值，与边界位置元素进行交换，直至待排序区间为空
         *  时间复杂度O(n*n)
         *  不稳定
         *  */
        // 1 预处理
        int n = arr.length;

        // 2 直接插入排序
        int left = 0;
        int right = n-1;
        while(left < right) {
            // -先价值i位置为最小值
            int minIndex = left;
            int maxIndex = left;
            for(int j = left+1; j <= right; j++) {
                // -找到最小值，记录其下标
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
                if(arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }
            // 3 找到待排序区间最小值，与当前位置元素进行交换（即当前位置有序）
            swap(arr, left, minIndex);
            if(left == maxIndex) {
                // -若是相等，则原本指向的值被交换到了minIndex
                swap(arr, right, minIndex);
            } else {
                // -不相等，正常交换
                swap(arr, right, maxIndex);
            }
            left ++;
            right --;
        }
    }

    public void heapSort(int[] arr) {
        /**
         * 堆排序
         *  后续补充，这个需要创建大根堆*/
    }

    public void bubbleSort(int[] arr) {
        /**
         * 冒泡排序
         *  每次将待排序区间中的最大值交换至队尾（单个有序）
         *  时间复杂度O(n*n)
         *  稳定*/
        // 1 预处理
        int n = arr.length;

        // 2 排序趟数，每一次排序，可以使最后一个元素有序
        for(int i = 0; i < n-1; i++) {
            // -一次排序可以使得最有一个元素有序，故每排序一次后，待排序区间缩小一个元素
            boolean flag = true;
            for(int j = 0; j < n-i-1; j++) {
                if(arr[j] > arr[j+1]) {
                    flag = false;
                    swap(arr, j, j+1);
                }
            }
            // -一趟下来没有任何交换，说明数组有序
            if(flag) {
                return;
            }
        }
    }

    public void quickSort(int[] arr) {
        /**
         * 快速排序-递归实现
         * */
        // -递归实现（之所以嵌套调用方法，是为了保证接口的统一）
        quick(arr, 0, arr.length-1);
    }

    private void quick(int[] arr, int left, int right) {
        /**
         * 快速排序-递归主体部分*/
        // 1 递归出口
        if(left >= right) {
            return;
        }
        // 2 找基准值
        int pivot = partition(arr, left, right);
        // 3 根据基准值递归排序左区间和右区间
        quick(arr, left, pivot-1);
        quick(arr, pivot+1, right);
    }

    private int partition(int[] arr, int left, int right) {
        /**
         * 快速排序-划分数组*/
        // 1 以区间最左边元素作为基准值（先记录）
        int baseValue = arr[left];
        int baseIndex = left;

        // 2 双指针划分区间
        while(left < right) {
            // -先步进右边再步进左边（为了保证最终值落在下雨等于基准值的区间，因为后续相遇点会与区间最左边进行交换）
            while(left < right && arr[right] >= baseValue) {
                right --;
            }
            while(left < right && arr[left] <= baseValue) {
                left ++;
            }
            // -出循环即是遇见不属于对应区间的值，交换
            swap(arr, left, right);
        }

        // 3 交换基准值位置
        swap(arr, baseIndex, left);
        return left;
    }

    public void mergeSort(int[] arr) {
        /**
         * 归并排序-接口层*/
        mergeSortFunction(arr, 0, arr.length-1);
    }

    private void mergeSortFunction(int[] arr, int left, int right) {
        /**
         * 归并排序-递归层*/
        // 1 递归出口
        if(left >= right) {
            return;
        }

        // 2 拆分待排序数组
        int mid = left + (right - left) / 2;
        mergeSortFunction(arr, left, mid);
        mergeSortFunction(arr, mid+1, right);

        // 3 二路归并
        twoWayMerge(arr, left, right, mid);
    }

    private void twoWayMerge(int[] arr, int s1, int e2, int e1) {
        /**
         * 二路归并*/
        // 1 创建变量
        int initialIndex = s1;
        int len = e2 - s1 + 1;
        int s2 = e1 + 1;

        // 2 将两个有序数组合并至临时数组中
        int[] tempArr = new int[len];
        int index = 0;
        while(s1 <= e1 && s2 <= e2) {
            if(arr[s1] <= arr[s2]) {
                tempArr[index++] = arr[s1++];
            } else {
                tempArr[index++] = arr[s2++];
            }
        }

        // 3 出循环将剩余元素全部入队
        while(s1 <= e1) {
            tempArr[index++] = arr[s1++];
        }
        while(s2 <= e2) {
            tempArr[index++] = arr[s2++];
        }

        // 4 将二路归并的数据同步至数组中
        for(int i = 0; i < len; i++) {
            arr[initialIndex + i] = tempArr[i];
        }
    }


    private void swap(int[] arr, int a,  int b) {
        /**
         * 交换函数（辅助）*/
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
